1. Field of the Invention
The invention in general relates to random number generators, and more particularly to a random number generator that generates true binary random sequences.
2. Description of the Related Art
It has become widely recognized that random number generators are fundamentally important in the computer age. See Stephen K. Park and Keith W. Miller, xe2x80x9cRandom Number Generators: Good Ones Are Hard To Findxe2x80x9d, in Computing Practices, October 1988, V. 31, No. 10, pp. 1192-1201. Random number generators may be divided into two types: true random number generators, which generate numbers from a non-deterministic source, and pseudorandom number generators, which generate numbers from a deterministic algorithm. A high quality random number generator is necessary for functions from Monte Carlo-based studies used in computer modeling of the global economy, to cryptography, to parapsychological studies, to marketing research, to lottery games. Thus, it is not surprising that the literature reveals hundreds of random number generators. See, for example, the following U.S. Pat. No. 3,423,683 issued to E. S. Kelsey et al.; No. 3,445,591 issued to D. R. Koehler et al.; No. 3,612,845 issued to Reed C. Lawlor; No. 3,706,941 issued to Charles E. Cohn; No. 3,725,677 issued to Reed C. Lawlor; No. 3,758,873 issued to Herbert E. Miller; No. 4,183,088 issued to Robert E. Simmons; No. 4,395,703 issued to Gerald V. Piosenka; No. 4,513,386 issued to Sydney Glazer; 4,578,598 issued to Mark E. Faulaber; No. 4,858,122 issued to William Kreisner; and No. 5,239,494 issued to Edmund C. Golbeck; and the following papers: Masatugu Isida and Hiroji Ikeda, xe2x80x9cRandom Number Generatorxe2x80x9d in Proceedings of the Institute of Statistical Mechanics, 1956, pp. 119-126; Helmut Schmidt, xe2x80x9cA Quantum Mechanical Random Number Generator for PSI Testsxe2x80x9d in The Journal of Parapsychology, circa 1972, pp. 219-224; and Teruyuki Izimi, xe2x80x9cUniversal Random Signal Generatorxe2x80x9d, in Electrical Engineering in Japan, Vol. 99, No. 4, 1979, pp. 124-130. Yet, there are few xe2x80x9crandom number generatorsxe2x80x9d on the market today that actually produce random numbers. High quality true random number generators are still in the realm of large-budget projects at major research institutions.
A random number generator (RNG) that interfaces directly with a computer would be of particular value since random numbers are often used in conjunction with a computer, and a direct interface allows a researcher or other computer user to simply call up the number generator and use the numbers it produces within the context of their program. See for example, James H. Macomber and Charles S. White, xe2x80x9cAn n-Dimensional Uniform Random Number Generator Suitable for IBM-Compatible Microcomputersxe2x80x9d, in Interfaces, Vol. 20, No. 3, May-June 1990, pp. 49-59. Because the most common computers today are digital, RNG""s that interface with computers generally generate a binary random sequence (BRS) rather than a sequence of analog or floating point numbers, which BRS""s may be used as generated, converted to uniform distributed numbers, converted to Gaussian distributed numbers or converted to any other type of distribution. Many computer programs that utilize random numbers are statistical in nature; that is, they depend on large numbers of events which are averaged in some manner to reach a valid conclusion. For this to be accomplished over reasonable time periods, these programs require that large quantities of binary bits or random numbers be generated in short periods. True random number generators usually trade off speed for randomness, thus are relatively slow. As a result, at this time it appears that the available random number generators that interface directly with computers are all software-based, pseudorandom number generators. See, Macomber and White, supra; Niederreiter, supra; and Park and Miller, supra.
While pseudorandom number generators are suitably fast for a computer, they cannot generate a true random number because they are generated by algorithms which are deterministic, i.e. they are totally predictable given knowledge of the algorithm used. In addition, most pseudorandom number generators used with computers produce number sequences which fail even moderately stringent statistical randomness tests. It is known that to generate a true random number, one must start with a non-deterministic signal, such as white noise generated by a resistor, diode, or other electronic device, the time between radioactive particle decay, the locations of detected photo-events, or other signal source that is essentially random because it is based on quantum mechanics or other statistically random process. See, for example, U.S. Pat. No. 4,176,399 issued to Jean-Claude Hoffmann et al., and the following papers: G. B. Agnew, xe2x80x9cRandom Sources For Cryptographic Systemsxe2x80x9d, in Lecture Notes in Computer Science-Advances in Cryptology-Eurocrypt""87, Springer-Verlag, Berlin, 1987, pp. 77-81; and Anthony J. Martino and G. Michael Morris, xe2x80x9cOptical Random Number Generator Based On Photoevent Locationsxe2x80x9d, in Applied Optics, Vol. 30, No. 8, 10 March 1991, pp. 981-989. We have referred to these signals as xe2x80x9cessentiallyxe2x80x9d random, because even these non-deterministic sources exhibit some defects because they are generated with macroscopic, real world devices.
It is known that the randomness in such non-deterministic signals can be improved by digital processing. See for example, U.S. Pat. No. 4,545,024 issued to David P. Maher et al., and the paper: Helmut Schmidt, xe2x80x9cQuantum-Mechanical Random-Number Generatorxe2x80x9d, in Journal of Applied Physics, Vol. 41, No. 2, February 1970, pp. 462-468. In particular it is known to improve randomness by using EXCLUSIVE OR X(OR) gates to discard certain bits. See, U.S. Pat. No. 4,355,366 issued to Sigmund N. Porter. It is also known to use comparators or other electronic devices to convert analog noise signals to binary signals. See, U.S. Pat. No. 4,545,024 cited above and H. Sutcliffe, xe2x80x9cNoise-spectrum Measurement at Subaudio Frequenciesxe2x80x9d, in Proceedings of the IEEE, Vol. 112, No. 2, February 1965, pp. 301-309.
Despite the fact that all of the above has been known for many years, a practical, inexpensive, fast, high-quality true random number generator that interfaces directly with a computer is not presently available. In fact, some authorities maintain that such a device is not practically possible. See, Harald Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, Chapter 7, section 7.2, p. 164, Society For Industrial and Applied Mathematics, Philadelphia 1992; and Aaldert Compagner, xe2x80x9cDefinitions of Randomnessxe2x80x9d, American Journal of Physics, Vol. 59, No. 8, August 1991, pp. 700-705, at page 702. As a result, xe2x80x9crandom number generatorsxe2x80x9d used with computers today are pseudo-random number generators.
The present invention solves the above problems by providing a true random number generator (RNG) in which the defects in randomness in the sequence generated are so small that one would have to run a test for trillions of years to demonstrate the defects with 95% confidence level. The random number generator plugs into the parallel port of any personal computer and is directly accessed via device driver software installed in the computer. The RNG is as easy to use as a printer, modem, or any other peripheral and is fast, producing a binary random sequence (BRS) of up to 10,000 bits per second, or 20,000 bits per second if a number of defects that could be demonstrated in several years at 95% confidence level is acceptable. Moreover, the device is inexpensive, costing little more than a modem or word-processing software.
The random number generator according to the invention amplifies the analog signal from a non-deterministic signal generator, passes it through a comparator to create a binary signal, which is sampled and stored in a shift register to create a digital signal. The randomness is then improved by using two levels of EXCLUSIVE OR (XOR) correction gates.
The source of the non-deterministic signal is preferably the thermal noise of a resistor, which has an essentially flat average amplitude versus frequency spectrum. The amplifier that amplifies the signal is a low-noise amplifier, so that the amplifier noise, which is not flat, contributes one-third or less of the total noise, preferably 25% or less. Prior to passing through the comparator, the signal is processed in several novel ways to improve its ability to generate random numbers. As is common in the amplifier art, the 1/F low-frequency tail of the amplifier noise is cut off with a high pass filter. However, the cut-off is made at a relatively low 100 Hertz (Hz) to include as much of the white noise spectrum as possible. That is, since the optimum spectrum from which to generate a random number is a white noise spectrum containing all frequencies, utilizing a relatively low high-pass filter decreases the defects in the final random number sequence. Further, the high frequency fall off that is common to op amps due to gain-bandwidth product limitations, is compensated for. Starting with a low-noise amplifier and compensating for the high frequency fall off helps keep the signal coming into the comparator essentially flat, preferably within xc2x10.25 db, over a wide bandwidth, preferably about 100 Hz to 100 kiloHerz (KHz). The comparator itself is a very high speed comparator, which retains the bandwidth of the analog section. The comparator offset is adjusted, preferably using a selectable resistor, so that there is a nearly equal number of high and low bits generated by the comparator. Thus, the binary signal produced by the comparator is a stable, highly random signal.
The sampling frequency is selected to be the optimum frequency to produce a high frequency stream of highly random binary bits. The sampling period is preferably selected to be at the knee of the serial dependence versus delay time curve, sometimes called the auto-correlation function. In the preferred embodiment of the invention this is 12.5 microseconds, which results in a bit stream at a frequency of 80,000 bits per second. Two levels of correction with the XOR gates decreases the defects in randomness to the extremely low levels mentioned above, and reduces the frequency to the 20,000 bits per second mentioned above. A third level of XOR function may be accomplished by software in the computer, reducing the bit rate to 10,000 per second.
It has been discovered that the randomness of an RNG producing a binary random sequence according to the invention can be predicted by the equations:
B2*=xe2x88x92SD(1); andxe2x80x83xe2x80x83(1)
SD(1)*xe2x89xa6SD(1)2+SD(2)2,SD(2)*xe2x89xa6SD(1)2 +SD(4)2,xe2x80x83xe2x80x83(2)
where SD(t) is the serial dependence as a function time, SD(1) indicates the first order serial dependence, that is the serial dependence at the first sample period, SD(2) second order serial dependence, etc., and B2 is the fractional bias in the 1, 0 probability given by the equation:
B2=[N(1)xe2x88x920.5N]/0.5N,xe2x80x83xe2x80x83(3)
where N(1) is the number of 1""s in a binary random sequence of length N. In equations (1) and (2) the star, *, indicates the statistic at the output of each level of XOR error correction while the unstarred values are those at the input of the error correction level. These equations were used to determine the number of levels of correction that were required to produce a stream of random numbers in which any lack of randomness could be detected given the measured amount of statistical defect at the XOR""s input. Thus, the use of equations 1 through 3 permit the design of the RNG to be optimized: enough randomness defect correction can be applied to remove any possibility of detecting non-randomness, but not excessive correction that would slow the device and add to its manufacturing cost.
The 20 kHertz stream of random bits is preferably converted into a 4-bit word with a shift register, latched, then sent to a buffer which isolates the random number generator from cable transients. An interrupt is generated when a 4-bit number is ready. A device driver in the computer recognizes the interrupt, reads the number and stores it in a memory buffer for use on demand by the user.
The entire random number generator is preferably mounted on a single small printed circuit board (PCB) which is adapted to be connected to and powered by the conventional parallel port of any personal computer. The power is taken off selected pins, preferably the 8-bit date output, of the parallel port while the ground is connected to the parallel port ground pins. The device driver installed in the computer simply applies the appropriate high signals to the selected pins to power the RNG. A negative voltage for the analog noise generator circuit is provided by charge pumps. Special circuits protect the RNG if the wrong voltages are applied to critical pins.
The RNG is isolated from external sources of non-randomness. As indicated above, the output drivers of the RNG are isolated from the random number generator itself to prevent any loading or interference output on the lines from feeding back into the RNG. The analog noise generator, the comparator, and the digital portions of the circuit have separate power supplies. All power supplies are filtered to remove transients.
A low amplitude portion of the circuitry is isolated from the normal amplitude circuitry and shielded to protect it from any external EMI or ESI source. The shield preferably comprises a ground plane on the PCB surrounding the low amplitude circuit, except for a small channel through which traces to the digital circuit pass, and a metal enclosure that encloses both sides of the board and bolts to the PCB with a flange on the enclosure contacting the ground plane. The flange also eliminates the effect of fringing through the thickness of the circuit board.
The device driver in the computer finds and tests the installed RNG each time the computer is turned on.
The invention provides a random number generator comprising: a computer having a parallel port, the parallel port including data and control lines; a random number generator circuit for producing a random sequence of signals, the random number generator circuit including power supply means for powering the circuit from power supplied by one or more of the data and control lines of the parallel port; and electrical connecting means for transferring power from the computer to the power supply means via the parallel port and for communicated signals generated by the random number generator circuit to the computer through the parallel port. Preferably, the power supply means comprises a charge pump. Preferably, the computer includes device driver means for operating the random number generator circuit through the parallel port. Preferably, the random number generator circuit includes a source of true random signals, the source being selected from the group consisting of: a thermal noise source; and an intrinsically random quantum source.
In another aspect, the invention provides a random number generator system comprising: a computer including a power source producing a first voltage of one sign; a charge pump for producing a second voltage of the opposite sign to the first voltage; and a random number generator circuit powered by the first and second voltages for generating a random sequence of signals. Preferably, the first voltage is a positive voltage, the second voltage is a negative voltage, and the charge pump comprises an analog multiplexer circuit.
In a further aspect the invention provides a random number generator comprising a circuit for generating a sequence of binary signals, and a computer for receiving the binary signals and utilizing them, the circuit using 30 milliwatts of power or less. Preferably, the circuit comprises: an analog noise generator for producing an analog noise signal; and a comparator, responsive to the analog noise signal, for providing the sequence of binary signals, the comparator: having a rise time up to 25 nanoseconds, drawing less than three milliamps of current, and operating down to 2 volts.
In another aspect the invention provides a random number generator circuit comprising: an analog noise generator; a charge pump for providing a voltage to the analog noise generator; an analog to binary converter for converting the analog noise to a binary signal; a randomness defect reducer for reducing randomness defects in the binary signal; and a buffer for driving the signal to an electronic device external of the random number generator circuit. Preferably, each of the charge pump, the analog noise generator, the analog to binary converter, the randomness defect reducer, and the buffer include a separately filtered power supply. Preferably, each of the charge pump, the analog noise generator, the analog to binary converter, the randomness defect reducer, and the buffer comprise a CMOS integrated circuit.
In still a further aspect, the invention provides a random number circuit for producing a sequence of binary signals, the circuit comprising: a source of a white noise electrical signal; and amplifier means for amplifying the white noise signal while adding an amplifier noise signal to the white noise signal; and wherein the amplifier noise is one-third or less of the total noise signal comprising the white noise signal and the amplifier noise signal. Preferably, the circuit further includes high pass filter means for removing a low-frequency tail in the total noise signal, the high pass filter means having a cut-off frequency in the range from 36 Hertz to 170 Hertz. Preferably, the total noise signal has a bandwidth of from 100 Hz to 100 KHz and is flat within xc2x10.25 db over the bandwidth.
In yet a further aspect, the invention provides a random number generator circuit for proving a sequence of binary signals, the circuit comprising: an analog noise generator for producing an analog noise signal; and comparator means, responsive to the analog noise signal, for providing the sequence of binary signals, the comparator means comprising an XHCU04 hex inverter, where X is 54 or 74.
In still another aspect, the invention provides a random number generator circuit comprising: a source of a white noise electrical signal; and amplifier means for amplifying the white noise signal, the amplifier means comprising one or more operational amplifiers selected from the group consisting of: TL06X operational amplifiers, where X is 0, 1, 2, or 4, LF44Y operational amplifiers, where Y is 1, 2, or 4, and AD548 and AD648 single and dual operational amplifiers.
The invention also provides a random number generator circuit comprising: a low amplitude circuit portion; a normal amplitude circuit portion; and an EMI shield enclosing the low amplitude circuit portion, wherein the low amplitude circuit portion is mounted on a printed circuit board and the shield comprises: a ground plane on the circuit board located around the low amplitude circuit portion in the plane of the circuit board, a component side cover and a solder side cover, the covers electrically connected to the ground plane.
In addition, the invention provides a random number generator comprising: a random number generator circuit for generating a random sequence of signals; and a computer including a means for interfacing with the random number generator circuit, the means for interfacing consisting of one or more of the following: a device driver, a TSR, a portion of the operating system of the computer, and a program stored in the bios memory of the computer. Preferably, the means for interfacing comprises a device driver and includes means for testing the random number generator circuit. The random number generator circuit is preferably located in a module separate from the computer, on an add-on board for mounting in the computer, on the motherboard of the computer, or on a peripheral of the computer.
In a further aspect, the invention provides a device for interfacing with a random number generator, the device comprising: a computer including: memory means for storing information for interfacing with a random number generator circuit, and processing means communicating with the memory for interfacing with the random number generator; and wherein the information for interfacing with a random number generator consists of one or more of the following: a device driver, a TSR, a portion of the operating system of the computer, and a program stored in the bios memory of the computer.
The invention also provides a random number generator comprising: a circuit for producing a sequence of binary signals; and sample means for sampling the sequence of binary signals at a sampling rate between 50% and 125% of the sampling rate at the knee on the serial dependence versus delay time curve describing the circuit to provide a random sequence of signals at the sampling rate. Preferably, the sampling rate is at the knee of the serial dependence versus delay time curve. Preferably, the random number generator further includes randomness defect reducer means for reducing the randomness defects in the sequence of binary signals.
The invention also provides a method of generating a random sequence of signals, the method comprising the steps of: providing a circuit for producing a sequence of signals; and sampling the sequence of signals at a sampling rate between 50% and 125% of a sampling rate corresponding to the knee on the serial dependence versus delay time curve describing the circuit to provide a random sequence of signals at the sampling rate. Preferably, the step of sampling comprises measuring a statistical parameter as a function of a time parameter related to the delay time of the random sequence of signals, the function having a knee where the character of the function changes from being essentially related to statistics to being essentially related to real physical characteristics of the circuit; and sampling the random sequence of signals at a sampling rate corresponding to a point on the function between 50% and 125% of the sampling rate at the knee to generate the random sequence of signals.
The invention also provides a method of designing and fabricating a random number generator, the method comprising the steps of: designing and making a circuit for producing a binary random sequence of signals; measuring a first parameter of the binary sequence of signals, the parameter related to the serial dependence of the binary random sequence; calculating the degree of defects in randomness in the sequence for one or more levels of defect correction to determine the optimum number of levels of defect correction to produce a random number generator with a desired randomness quality; and fabricating a random number generator comprising the circuit and the optimum number of levels of defect correction. Preferably, the step of calculating comprises calculating the degree of defects in randomness as a function of a second parameter related to the delay time to determine the optimum number of levels for different values of the second parameter; and the step of fabricating comprises fabricating a random number generator having an optimum number of levels for a selected delay time. Preferably, the first parameter comprises one or more parameters selected from the group consisting of B2 and SD(t) and the second parameter comprises a parameter selected from the group consisting of delay time and sample rate. Preferably, the step of fabricating includes providing at least one level of defect correction comprising EXCLUSIVE OR gate means for combining pairs of consecutive binary signals in the sequence of signals. Alternatively, the step of fabricating includes providing at least one level of defect correction comprising a divider.
The invention also provides a method of generating a sequence of random numbers, the method comprising the steps of: providing a circuit for producing a binary random sequence of signals; measuring a parameter of the binary sequence of signals, the parameter related to the serial dependence of the binary random sequence; calculating the degree of defects in randomness in the sequence for one or more levels of defect correction to determine the optimum number of levels of defect correction for a desired randomness quality; and reducing the defects in the binary random sequence of signals by providing the optimum number of levels of defect correction.
The invention not only provides a high-quality true random number generator that interfaces easily with a personal computer, it also does this in a manner that allows the random number generator to be manufactured relatively inexpensively. Numerous other features, objects and advantages of the invention will become apparent from the following description when read in conjunction with the accompanying drawings.